package BackTrackingPackage2;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combinationSum_ {
  List<List<Integer>> result = new ArrayList<>();
  List<Integer> list = new ArrayList<>();
  @Test
  public void combinationSumTest(){
    int[] candidates = new int[]{2,3,6,7};
    combinationSum(candidates,7);
    for (List<Integer> integers : result) {
      System.out.println(integers.toString());
    }
  }

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    backTracking(candidates,target,0);
    return result;
  }

  public void backTracking(int[] candidates, int target,int startIndex){
    if (getSum(list) == target){
      result.add(new ArrayList<>(list));
      return;
    }
    if (getSum(list) >= target){
      return;
    }
    for (int i = startIndex ; i < candidates.length ; i ++){
      list.add(candidates[i]);
      backTracking(candidates,target,i);
      list.remove(list.size() - 1);
    }
  }
  public int getSum(List<Integer> path){
    int sum = 0;
    if (path.size() != 0 && path != null){
      for (Integer integer : path) {
        sum += integer;
      }
    }
    return sum;
  }
}
